package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author zhangjy
 * @description 在每个树行中找最大值
 * @date 2025/4/7 13:20
 */
public class LargestValues_515 {

    /**
     * DFS-参照官解；
     * <p>
     * 按照先序遍历递归；
     * <p>
     * 时间复杂度：T(n) = O(n)；其中，n是节点个数，每个节点只会被访问一次。
     * 空间复杂度：S(n) = O(n)；其中，广度优先遍历的复杂度取决于一个层级上的最大元素数量。最坏情况下，一个满二叉树最后一层的节点数为N/2，这种情况的空间复杂度为 O(N)。
     */
    public List<Integer> largestValues2(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;

        dfs(root, ans, 0);
        return ans;
    }

    public void dfs(TreeNode node, List<Integer> ans, Integer layer) {
        if (node == null) return;

        if (layer == ans.size()) {
            // 本层首次访问节点，则直接记录
            ans.add(node.val);
        } else {
            // 不是首次，则取节点最大值
            ans.set(layer, Math.max(ans.get(layer), node.val));
        }
        layer++;

        // 向下递归
        dfs(node.left, ans, layer);
        dfs(node.right, ans, layer);
    }

    /**
     * 个解-BFS；
     * <p>
     * 思路：出栈时每次把一层节点全部出栈，同时记录本层节点最大值。
     * <p>
     * 时间复杂度：O(n)；其中，n是节点个数，每个节点仅会进出队列一次；
     * 空间复杂度：S(n)；存储二叉树节点的开销。
     */
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) return ans;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int curLayerSize = queue.size();
            int curLayerMax = Integer.MIN_VALUE;
            // 遍历每层节点，取最大值
            for (int i = 0; i < curLayerSize; i++) {
                TreeNode poll = queue.poll();
                curLayerMax = Math.max(poll.val, curLayerMax);

                // 非空入栈下一层
                if (poll.left != null) queue.offer(poll.left);
                if (poll.right != null) queue.offer(poll.right);
            }
            ans.add(curLayerMax);
        }

        return ans;
    }

}
